Codeforces Round #563 Div2 A~D题解

本场链接:Codeforces Round #563
本场的EF题都到了2500/2400的难度,我爬了

A. Ehab Fails to Be Thanos
题目大意:给定一个长度2n2n的序列,问你是否有可能通过重排这个序列,使得他的前nn个元素的和后nn个元素的和不一样.如果可以,则额外输出具体方案是什么.

很显然,如果整个序列排序了,则两边的和如果仍然相同,则必然是一个全相同的序列,原问题无解.否则直接输出排序后的结果就可以了.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
int a[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 0;i < 2 * n;++i)	scanf("%d",&a[i]);
	sort(a,a + 2 * n);
	int ok = 1,l = 0,r = 0;
	for(int i = 0;i < n;++i)	l += a[i];
	for(int i = n;i < 2 * n;++i)	r += a[i];
	if(l == r)	puts("-1");
	else 
		for(int i = 0;i < 2 * n;++i)	printf("%d ",a[i]);

	
    return 0;
}

B. Ehab Is an Odd Person
题目大意:给一个长度为nn序列,对任意的两个位置i,ji,j,如果有ai+aja_i + a_j是奇数,就可以交换aia_iaja_j,问经过若干次的操作之后,可以得到的字典序最小的序列是什么.

显然,如果一个序列只有奇数或者偶数,就一下都换不了,原序列就是最小的序列了.反之,如果既有奇数又有偶数,可以发现,如果拿任意一个偶数作为跳板,就可以任意的交换所有的元素,奇数也是同理.因此如果既有奇数又有偶数,最小字典序的序列就是排序后的序列,直接输出即可.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int a[N],n;

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
	int odd = 0,even = 0;
	for(int i = 1;i <= n;++i)
	{
		if(a[i] & 1)	odd = 1;
		else even = 1;
	}
	if(odd && even)	sort(a + 1,a + n + 1);
    for(int i = 1;i <= n;++i)	printf("%d ",a[i]);
    return 0;
}

C. Ehab and a Special Coloring Problem
题目大意:已知两个正整数nnkk,对于在22nn之间的任意ii,给这个位置一个值aia_i,要满足如下两个性质:
①对于任意的两个互质的数iijj,需要满足aiaja_i \ne a_j.
②所有aia_i的最大值应该尽量小.

数据范围:
2n1052 \leq n \leq 10^5
1ain1 \leq a_i \leq n

这题由于两两互质的条件比较强,而且暴力的判断每对数肯定是不行的.这肯定要另找出路,很容易想到筛质数里的筛法操作,这里也是同理:对于一个质数pp显然可以把他所有的倍数全部和他染成一个颜色,这个在筛法里套一个循环就可以了.但是怎么确定颜色有哪些呢?其实顺着上面那个思路就可以想到说:对于一个合数,他和一个质数一起一定是互质的,因此每碰到一个质数,就把染色的数字加一,再往后筛.其次如果两个合数互质的话,说明他俩里面没有相同的质因子,也就是说,他俩一定是由两个不同的质数的颜色翻上来的.所以这个方法是正确的.之后还有一步贪心也就非常顺利成章了:对于每个数,肯定只取最小的质因子染过来的色,因为要使整个序列的所有aia_i的最大值最小,可以发现这个最大值必然只是质数的个数,而且肯定也不能再减少了.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],st[N],cnt;
int col,res[N];
void init()
{
	for(int i = 2;i < N;++i)
	{
		if(!st[i])	
		{
			primes[cnt++] = i;
			++col;
			for(int j = 1;j * i < N;++j)	
				if(res[i * j] == 0)
					res[i * j] = col;
		}
		for(int j = 0;j < cnt && primes[j] * i < N;++j)
		{
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0)	break;
		}
	}
}
int main()
{
	init();
	int n;scanf("%d",&n);
	for(int i = 2;i <= n;++i)	printf("%d ",res[i]);
    return 0;
}

D. Ehab and the Expected XOR Problem
题目大意:给定两个正整数nnxx,构造一个满足如下要求的序列aa
①所有元素的值[1,2n)\in [1,2^n)
②不存在一个子段的异或和是00或者xx
③整个序列aa的长度要尽量长.
输出长度以及具体方案.
注意:子段的定义是把aa序列的开头和结尾各删掉一段连续的序列,当然可以不删,剩下的就是子段.

数据范围:
1n181 \leq n \leq 18
1x2181 \leq x \leq 2^{18}

直接构造这个序列必然很困难,考虑用异或前缀和的方式曲线救国:
定义异或前缀和序列bi=aiai1b_i = a_i \oplus a_{i-1},则原有的ai=bibi1a_i = b_i \oplus b_{i-1}.
其次,题目里的条件依次可以这样转换:
bib_i的值[1,2n)\in [1,2^n),因为异或后的值必然不会超过2n2^n,所以如此还原的aa序列的值最终也还是属于这个区间的.
②不存在两个相同的bib_i,以及bi=xb_i = xbi=0b_i = 0.因为整个子段其实就是两个前缀异或和再异或一次的结果,如果两个bib_i相同,说明这两个夹着的中间子段是00,其次不能是xx,只要没有一个xx或者00就可以满足不存在xx了.不过由于bi1b_i \geq 1 ,所以00这个条件可以不显式的写出来.
③尽量把所有满足的全填进去.

我们来考虑一下这个bb怎么构造的:首先肯定要把xx00打上标记去掉,其次,对于每一个在[1,2n)[1,2^n)这个区间的值ii,我们都是可以加进去的,但是如果他加进去了,就不能再加ixi\oplus x了,直接标记iiixi\oplus x即可.整个流程也就非常显然了,即遍历整个范围,找到一个没标记的ii,把他加入序列,再把他和异或xx的值一起标记掉.最后还原整个aa序列输出即可.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 19);
int st[N];
int main()
{
	int n,x;scanf("%d%d",&n,&x);
	st[0] = st[x] = 1;
	vector<int> res;
	for(int i = 1;i < (1 << n);++i)
	{
		if(st[i])	continue;	
		res.push_back(i);
		st[i] = 1;
		st[i ^ x] = 1;
	}
	for(int i = res.size() - 1;i >= 1;--i)	res[i] = res[i] ^ res[i - 1];
	printf("%d\n",res.size());
	for(int i = 0;i < res.size();++i)
		printf("%d ",res[i]);
    return 0;
}